BZOJ3442 学习小组 <费用流>

Problem

学习小组

Time Limit:
Memory Limit:

Description

坑校准备鼓励学生参加学习小组。
共有个学生，个学习小组，每个学生有一定的喜好，只愿意参加其中的一些学习小组，但是校领导为学生考虑，规定一个学生最多参加个学习小组。财务处的大叔就没那么好了，他想尽量多收钱，因为每个学生参加学习小组都要交一定的手续费，不同的学习小组有不同的手续费。然而，事与愿违，校领导又决定对学习小组组织者进行奖励，若有个学生参加第i个学习小组，那么给这个学习小组组织者奖励元。在参与学生（而不是每个学习小组的人数总和）尽量多的情况下，求财务处最少要支出多少钱（若为负数，则输出负数）（）。

Input

输入有若干行，第一行有三个用空格隔开的正整数。接下来的一行有个正整数，表示每个。第三行有个正整数，表示参加每个学习小组需要交的手续费。再接下来有一个行列的矩阵，表若第行列的数字是，则表示第个学生愿意参加第个学习小组，若为，则为不愿意。

Output

输出只有一个整数，为最小的支出。

Sample Input

Sample Output

-2

Hint

样例解释
参与学生最多为，每个学生参加一个学习小组，若有两个学生参加第一个学习小组，一个学生参加第二个学习小组（一定要有人参加第二个学习小组），支出为，可以证明没有更优的方案了。
数据范围与约定
的数据，。

标签：费用流

Solution

常规费用流建模。
建图：
每个学生为一个点，每个小组为一个点，共个点。
对每个学生，
流量费用（限制最多选个组）
流量费用（限制至少选一个组）
对每个组，
流量费用其中
即当前若有个人，再多一个人会带来的收益
学生和组之间则连边流量费用
跑小费流即可。

Code

#include <bits/stdc++.h>
#define MAX_N 500
#define MAX_M 50000
#define INF 0x7f7f7f7f
using namespace std;
int n, m, k, s, t, cnt, pr[MAX_N+5], cr[MAX_N+5], mxf, mic;
struct node {int v, c, w, nxt;} E[MAX_M+5];	int f[MAX_N+5];
void init() {s = 0, t = n+m+1, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c, int w) {E[cnt] = (node){v, c, w, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c, int w) {insert(u, v, c, w), insert(v, u, 0, -w);}
bool SPFA() {
    queue <int> que;	bool inq[MAX_N+5];	int d[MAX_N+5], cr[MAX_N+5];
    memset(inq, false, sizeof inq), memset(d, INF, sizeof d);
    d[s] = 0, que.push(s), inq[s] = true, memset(cr, -1, sizeof cr);
    while (!que.empty()) {
        int u = que.front();	que.pop(), inq[u] = false;
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c, w = E[i].w;
            if (c && d[u]+w < d[v]) {
                d[v] = d[u]+w, cr[v] = i;
                if (!inq[v]) que.push(v), inq[v] = true;
            }
        }
    }
    if (d[t] == INF) return false;	int flow = INF;
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) flow = min(flow, E[i].c);
    for (int i = cr[t]; ~i; i = cr[E[i^1].v]) E[i].c -= flow, E[i^1].c += flow;
    mxf += flow, mic += d[t];	return true;
}
int main() {
    scanf("%d%d%d", &n, &m, &k), init();
    for (int i = 1; i <= n; i++) addedge(s, i, k, 0);
    for (int i = 1; i <= n; i++) addedge(i, t, k-1, 0);
    for (int i = 1; i <= m; i++) {
        int c;	scanf("%d", &c);
        for (int j = 1; j <= n; j++)
            addedge(i+n, t, 1, c*(2*j-1));
    }
    for (int i = 1; i <= m; i++) scanf("%d", f+i);
    for (int i = 1; i <= n; i++) {
        char s[MAX_N];	scanf("%s", s+1);
        for (int j = 1; j <= m; j++) if (s[j] == '1')
            addedge(i, j+n, 1, -f[j]);
    }
    while (SPFA()) ;	return printf("%d", mic), 0;
}